From zk-SNARKs to zk-STARKs: The Application of Zero-Knowledge Proofs

• Using Zero-Knowledge Proofs
• What Is a zk-SNARK?
• zk-SNARK Issues
• What Is a zk-STARK?
• What Do zk-STARKs Fix?
• Current Limitations with zk-STARKs
• Uses Cases and Implementation

There is a growing focus on improving privacy within the cryptocurrency space. Bitcoin, Ethereum, Bitcoin Cash, and Litecoin are all actively looking for the most appropriate ways to increase their privacy and with it, fungibility. No longer are privacy-focused projects like Monero and Zcash the only ones fighting to increase our ability to stay anonymous.

Using Zero-Knowledge Proofs

Many people have long seen zero-knowledge proofs as an appropriate avenue for increased privacy. Zero-knowledge proofs are methods of proving something while only divulging a very small amount of information about that something. zk-SNARKs are one form of applying zero-knowledge proofs. The Zcash team has been at the forefront of implementing them. Ethereum developers are also considering zk-SNARKs as one way to implement such proofs.

However, there have been some major flaws. The main problem has been the need for a trusted setup. zk-SNARKs rely on a permissioned private key. This essentially undermines the entire purpose of decentralized public blockchains. By introducing the need to trust a person rather than code, you threaten the entire concept of trustlessness.

Fortunately, a more recent development called zk-STARKs has shown a way to achieve the same level of privacy as zk-SNARKs without the need for the trusted setup. If developers can successfully implement this, zk-STARKs could provide a privacy solution that offers some of the best anonymity available. It would also be fully trustless, more scalable, and secure.

What Is a zk-SNARK?

A zk-SNARK is a zero-knowledge succinct non-interactive argument of knowledge. When applied to a cryptocurrency, it means you can hide all of the transaction data. This includes the sender address, receiver address, as well as the transaction amount. zk-SNARKs allow us to hide all of this information, while also allowing the network to confirm and verify the transactions. It maximizes privacy while maintaining consensus.

In terms of blockchain level privacy, this is truly remarkable. It’s one of the most advanced blockchain level privacy technology in use. Of course, this does nothing to protect users at the network level. For this, it’s necessary to integrate protections such as Tor or I2P.

zk-SNARK Issues

There are, however, several issues with zk-SNARKs. The first is our trusted setup problem. The proofs rely on a common string that ensures the legitimacy of the zero-knowledge proofs. Various people participated in the process that created this string. So, in short, the privacy of the system depends on these individuals not disclosing the details of this aforementioned process. According to the Zcash team, who right now are the main users of this technology, the process was conducted with different parties participating from different locations. Ultimately, you have to assume and hope that these individuals have not or will not compromise this setup. If they were to do so, it would compromise the entire privacy of zk-SNARKs.

Commentators have observed that as the value of blockchains and their native assets that rely on zk-SNARKs increases, the incentive for malicious parties to entice or force the original actors to hand over the details to this setup increases. Ultimately, it seems that regardless of the number of audits that developers conduct on the setup, since it relies on the good acting of these initial people, it likely will not be used in the mainstream.

What Is a zk-STARK?

A zk-STARK is a zero-knowledge scalable and transparent argument of knowledge. Notice the key differences to zk-SNARKs, namely scalability and transparency.

The idea was proposed by Eli Ben-Sasson and has been expanded upon with his coauthors in their white paper. Ben-Sasson has founded his own company, StarkWare Industries, that is focused on the research and application of zk-STARKs to blockchains of all kinds.

The innovations of Ben-Sasson created zk-STARKs to provide proofs that can be verified much faster than previously thought. What is more, they actually scale exponentially relative to the data set they are representing, whether that be a blockchain asset, documents, or other datasets.

Right now, Monero, Zcash, and Ethereum are all seriously considering zk-STARKs.

What Do zk-STARKs Fix?

First and foremost, zk-STARKs have solved the trusted setup problem. They completely remove the need for multiple parties to create the private key needed for the string. Instead, everything needed to generate the proofs is public and the proofs are generated from random numbers. zk-STARKs actually remove the requirement in zk-SNARKs for asymmetric cryptography and instead use the hash functions similar to those found in Bitcoin mining.

Beyond this, they should have a longer shelf life in terms of their cryptographic resilience than zk-SNARKs. Right now, zk-STARKs are considered to be resistant to advances in quantum computing. In contrast, the elliptic-curve cryptography that underpins zk-SNARKs is susceptible to the advances in computing power that quantum computing could pose.

Quantum computers are able to decipher private keys from public keys far faster than legacy computers. This is due to the differences between bits (0 or 1) and qubits (0 and 1 at the same time). Elliptic-curve cryptography is what we typically use to generate private and public keys and is not quantum-resistant. zk-STARKs, in contrast, do not use this type of cryptography and are therefore safe from such advances.

Current Limitations with zk-STARKs

The main issue with zk-STARKs is their size. Currently, the proofs it uses are simply too big to use in most blockchains as they stand. According to Vitalik Buterin, zk-STARKs will result in proofs of a few hundred kilobytes versus the 288 bytes seen in zk-SNARKs. However, there is no reason to think developers will not solve this size issue. Indeed, compression of privacy features has been moving quickly, such as the implementation of Bulletproofs in the case of Confidential Transactions and Zcash’s Sapling upgrade for zk-SNARKs.

[thrive_leads id=’5219′]

Uses Cases and Implementation

Right now, no public blockchain has integrated zk-STARKs. Though, it is likely that they will find themselves in Zcash or Monero over the coming years and possibly Ethereum, also.

Buterin has spoken about his concerns around Ethereum’s lack of privacy and has had a significant interest in integrating zk-SNARKs. However, considering the advantages of zk-STARKs, it looks increasingly likely that Buterin and others will consider them. In fact, in July 2018, the Ethereum foundation awarded StarkWare Industries a grant. The hope is that further development could help fix Ethereum’s lack of privacy.

Monero is apparently looking at zk-STARKs for a later date. If we see more research to reduce the size of the proofs, it is likely they will implement them.

Of course, outside of the cryptocurrency space, businesses and projects could realize their benefits. Ben-Sasson believes that businesses could increase the security and privacy of either their own or customer’s data while maintaining a degree of public transparency.